MIME-Version: 1.0
Server: CERN/3.0
Date: Wednesday, 2cp: No match.
:57 GMT
Content-Type: text/html
Content-Length: 8782
Last-Modified: Thursday, 10-Oct-96 00:17:32 GMT

<html>
<head>
<TITLE>Jon Kleinberg's Homepage</TITLE>
</head>
<body>

<h1> Jon Kleinberg </h1>
<i>
<dl>
<dt> <!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><a href="mailto:kleinber@cs.cornell.edu">kleinber@cs.cornell.edu</a>
<dt> Assistant Professor of <!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><a href="http://www.cs.cornell.edu">Computer Science</a>
<dt> <!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><a href="http://www.cornell.edu">Cornell University</a>
<dt> Ithaca, NY  14853-7501
</dl>
</i>

My research interests are in algorithms and combinatorial optimization,
with an emphasis on approximation, computational geometry, 
network optimization and distributed computing, and 
algorithms in molecular biology.
Recent work has included<P>

<LI> approximation algorithms for routing and
disjoint paths problems in networks;
<LI> adversarial queueing theory, an approach to analyzing the stability
of network routing protocols without probabilistic assumptions;
<LI> geometric methods in combinatorial optimization, particularly
the use of positive semi-definite programming; and
<LI> geometric algorithms for studying molecular conformation.<P>

I am spending the 1996-97 academic year visiting the 
<!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><A HREF="http://www.almaden.ibm.com/almaden/">IBM Almaden 
Research Center.</A><P>

Click here to see
<UL>
<LI><b><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><A HREF="#papers">Selected Publications</A></b>
<LI><b><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><A HREF="#links">Miscellaneous Links</A></b>
</UL>
<P>

<H2><A NAME = "papers">PAPERS</a></H2>

<H3>Approximation Algorithms and Combinatorial Optimization</H3>

<LI> J. Kleinberg.  <!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs96-uf.ps">Single-source unsplittable flow.</A>
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,
to appear.<P>

<LI> J. Kleinberg, R. Rubinfeld.  <!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs96-exp.ps">Short paths 
in expander graphs.</A>
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,
to appear.<P>

<LI> J. Kleinberg, E. Tardos.  <!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs95.ps">Disjoint
paths in densely embedded graphs.</A>
Proc. 36th IEEE Symposium on Foundations of Computer Science,
1995.  <P>

<LI> J. Kleinberg, E. Tardos.  <!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/stoc95.ps">Approximations 
for the disjoint paths problem in high-diameter planar networks.</A>
Proc. 27th ACM Symposium on Theory of Computing, 1995.<P>

<LI> A. Aggarwal, J. Kleinberg, D. Williamson.  <!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/stoc96-node.ps">Node-disjoint
paths on the mesh, and a new trade-off in VLSI layout.</A>
Proc. 28th ACM Symposium on Theory of Computing, 1995.<P>

<LI> M. Goemans, J. Kleinberg.  <!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/soda96-latency.ps">An improved
approximation ratio for the minimum latency problem.</A>
Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 1996.<P>

<LI> J. Kleinberg, M. Goemans.  <!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/theta.ps">The Lovasz theta
function and a semi-definite programming relaxation of vertex cover.</A>
To appear in SIAM J. Discrete Math.<P>

<H3>On-Line Algorithms</H3>

<LI> J. Kleinberg.  <!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs94.ps">The localization problem for
mobile robots.</A>  Proc. 35th IEEE Symposium on Foundations of Computer
Science, 1994.<P>

<LI> J. Kleinberg.  <!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/soda94-search.ps">On-line search in a simple
polygon.</A>  Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.<P>

<LI> J. Kleinberg.  <!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/ipl-bal.ps">A lower bound for two-server
balancing algorithms.</A>  Information Processing Letters 51(1994).<P>

<LI> R. El-Yaniv, J. Kleinberg.  <!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/ipl-plane.ps">Geometric two-server
algorithms.</A>  Information Processing Letters 53(1995).<P>

<LI> J. Kleinberg.  <!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/ms.ps">On-line algorithms for robot
navigation and server problems.</A>  MIT/LCS/TR-641.  (Master's Thesis.)<P>

<H3>Parallel and Distributed Computing</H3>

<LI> D.M. Andrews, B. Awerbuch, A. Fernandez, 
J. Kleinberg, F.T. Leighton, Z. Liu.
<!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/focs96-aqt.ps">Universal stability results for greedy 
contention-resolution protocols.</A>
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996,
to appear.<P>

<LI> A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, D. Williamson.
Adversarial queueing theory.
Proc. 28th ACM Symposium on Theory of Computing, 1995.<P>

<LI> J. Kleinberg, H. Attiya, N. Lynch.  <!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/istcs95.ps">Trade-offs
between message delivery and quiesce times in connection management
protocols.</A>  Proc. 3rd Israel Symposium on Theory of Computing and Systems,
1995.<P>

<LI> J. Kleinberg, S. Mullainathan.  <!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/podc93.ps">Resource bounds
and combinations of consensus objects.</A>  Proc. 12th ACM Symposium on
Principles of Distributed Computing, 1993.<P>

<H3>Geometric Algorithms</H3>

<LI> B. Berger, J. Kleinberg, F.T. Leighton.  Reconstructing a
Three-Dimensional Model with Arbitrary Errors.
Proc. 28th ACM Symposium on Theory of Computing, 1995.<P>

<LI> D. Huttenlocher, J. Kleinberg.  <!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/soda94-proj.ps">Comparing 
point sets under projection.</A>  Proc. 5th ACM-SIAM Symposium on 
Discrete Algorithms, 1994.<P>

<LI> D. Huttenlocher, K. Kedem, J. Kleinberg.  <!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/geom92.ps">On 
dynamic Voronoi diagrams and the minimum Hausdorff distance for point
sets under Euclidean motion in the plane.</A>  Proc. 8th ACM Symposium
on Computational Geometry, 1992.<P>

<LI> D. Huttenlocher, J. Kleinberg,  <!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><A HREF="http://www.cs.cornell.edu/Info/People/kleinber/iv.ps">Invariants
of set of points or line segments under projection.</A>  Cornell University
Computer Science Technical Report TR 92-1292, July 1992.<P>

<H2><A NAME = "links">SOME LINKS</a></H2>

<H3>Search Tools and Bibliographies</H3>

<UL>
<li><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><A HREF="http://altavista.digital.com/">AltaVista.</A>
<li><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><A HREF="http://guide.infoseek.com/Home?page=Home.html&sv=N2">Infoseek.</A>
<li><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><A HREF="http://www.excite.com/">Excite.</A>
<li><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><A HREF="http://www.yahoo.com/">Yahoo.</A>
<li><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><A HREF="http://s18.bigyellow.com/">NYNEX Yellow Pages.</A>
<li><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><A HREF="http://glimpse.cs.arizona.edu:1994/bib/">Glimpse computer science bibliographies.</A>
<li><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><A HREF="http://cs-tr.cs.cornell.edu/">NCSTRL: Networked Computer Science Technical Reports Library.</A> 
<li><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><A HREF="http://theory.lcs.mit.edu/~dmjones/hbp/">David Jones's Hypertext Bibliography Project.</A>
</UL>

<H3>Academic Sites</H3>

<UL>
<li><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><A HREF="http://www.cornell.edu/">Cornell University.</A>
<li><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><A HREF="http://www.cs.cornell.edu">Cornell Computer Science.</A>
<li><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><A HREF="http://www.orie.cornell.edu">Cornell Operations Research.</A>
<li><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><A HREF="http://www.lcs.mit.edu">MIT Lab for Computer Science.</A>
<li><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><A HREF="http://theory.lcs.mit.edu">MIT LCS Theory of Computation Group.</A>
<li><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><A HREF="http://www-cs.stanford.edu">Stanford Computer Science.</A>
<li><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><A HREF="http://www.cs.berkeley.edu">Berkeley Computer Science.</A>
<li><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><A HREF="http://cra.org/">Computing Research Association.</A>
<li><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><A HREF="http://www.nsf.gov/">National Science Foundation.</A>
</UL>

<H3>Theory of Computing</H3>

<UL>
<li><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><A HREF="http://sigact.acm.org/tcs-rolodex/">TCS Virtual Address Book.</A>
<li><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><A HREF="http://liinwww.ira.uka.de/bibliography/Theory/index.html">Bibliographies on Theory/Foundations of Computer Science.</A>
<li><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><A HREF="http://www.nada.kth.se/~viggo/problemlist/compendium.html">Crescenzi/Kann Compendium of NP Optimization Problems.</A>
<li><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><A HREF="http://www.umiacs.umd.edu:80/events/FOCS96/">1996 FOCS conference.</A>
<li><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><A HREF="http://www.siam.org/meetings/da97/da97home.htm">1997 SODA conference.</A>
<li><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><A HREF="http://hercule.csci.unt.edu:80/stoc97/">1997 STOC conference.</A>
</UL>

<H3>Computational Biology</H3>

<UL>
<li><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><A HREF="http://www-hto.usc.edu/index.html">Computational Biology at USC.</A>
<li><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><A HREF="http://iris4.carb.nist.gov/">CARB Biocomputing Resources.</A>
<li><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><A HREF="http://gn.sdsc.edu:70/1/CCMS/Servers">SDSC's List of Computational Biology Servers.</A>
</UL>

<H3>Computational Geometry</H3>

<UL>
<li><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><A HREF="http://www.ics.uci.edu/~eppstein/junkyard/">David Eppstein's Geometry Junkyard.</A>
<li><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><A HREF="http://www.cs.duke.edu/~jeffe/compgeom/">Jeff Erickson's Computational Geometry Page.</A>
</UL>

<H3>Internet Security</H3>

<UL>
<li><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><A HREF="http://www.mitre.org/resources/centers/infosec/public-secur
ity-index.html">MITRE Corp.'s Security Information Resources.</A>
<li><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><A HREF="http://www.cs.princeton.edu/sip/">Princeton Safe Internet Programming Group.</A>
<li><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><A HREF="http://theory.lcs.mit.edu/~rivest/crypto-security.html">Ron Rivest's Cryptography and Security Links.</A>
</UL>

<H3>Miscellaneous</H3>

<UL>
<li><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><A HREF="http://home.netscape.com/">Netscape.</A>
<li><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><A HREF="http://www.intellicast.com/weather/usa">Intellicast.</A>
<li><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><A HREF="http://www.cnn.com/">CNN Interactive.</A>
<li><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><A HREF="http://www.usta.com/">U.S. Tennis Association.</A>
<li><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><A HREF="http://www.uschess.org/">U.S. Chess Online.</A>
<li><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><A HREF="http://www.cartalk.com/">Car Talk.</A>
</UL>




<ADDRESS>Jon M. Kleinberg</ADDRESS>
<ADDRESS>Department of Computer Science</ADDRESS>
<ADDRESS>Upson Hall</ADDRESS>
<ADDRESS>Cornell University</ADDRESS>
<ADDRESS>Ithaca, NY 14853</ADDRESS>
<ADDRESS>(607)255-4117</ADDRESS>
<ADDRESS>kleinber@cs.cornell.edu</ADDRESS>

